{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### 1. 请简述基于内容的推荐和基于协同过滤的推荐的基本原理，并指出二者的适用场景。（20分）\n",
    "+ 基于内容的推荐\n",
    "    + 原理是完全根据User的内容特征，得到User画像；通过Item的内容特征，得到Item画像；然后通过监督学习方法，拟合出User画像和Item画像之间的关系模型，进而根据这个模型来预测User对新的Item的打分，再根据打分排序，得到推荐给User的Item列表。它的特点是完全基于User和Item的历史特征来对未来进行预测。\n",
    "    + 适用场景: 完全基于个人的行为，不考虑其他用户的行为; User和Item画像都比较鲜明的情形；\n",
    "\n",
    "+ 基于协同过滤的推荐\n",
    "    + 原理是不考虑User和Item的个体特征，而只考虑历史上User和Item之间的交互行为，根据行为的统计数据，对User之间的相似性和Item之间的相似性做出定量估计，然后根据相似性作为基础，再对User推荐新的Item。\n",
    "    + 适用场景：有较为丰富的User和Item交互历史数据产生的平台，非冷启动的情况; 需要推荐一定量的新Item，来为User提高新鲜度和惊喜度的场景"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2. 请分别给出一个基于用户的协同过滤和基于物品的协同过滤的典型应用场景。（20分）\n",
    "+ 基于用户的协同过滤场景<br/>\n",
    "新闻应用, 这里的新闻是Item, 每天大量产生，但User的喜好相对稳定，所以计算User的相似性比计算Item的相似性更方便、更有效；\n",
    "<br/>\n",
    "+ 基于物品的协同过滤场景：<br/>\n",
    "电商平台，这里的电商物品是Item，总量有限，但User很多，而且User的喜好也比较丰富，又由于对推荐实时性的要求，所以计算Item的相似性可以离线进行，比计算User的相似性更方便、更有效。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3. 将推荐电影数目改成20个，运行课程给的代码，比较三种协同过滤算法的性能，并和推荐数目为10的推荐结果比较。（60分）\n",
    "+ 基于User的CF\n",
    "\n",
    "```\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "# load数据（用户和物品索引，以及倒排表）\n",
    "import _pickle as cPickle\n",
    "\n",
    "# 稀疏矩阵，打分表\n",
    "import scipy.io as sio\n",
    "import os\n",
    "\n",
    "# 距离\n",
    "import scipy.spatial.distance as ssd\n",
    "import time\n",
    "\n",
    "# 用户和item的索引\n",
    "users_index = cPickle.load(open(\"./out/users_index.pkl\", 'rb'))\n",
    "items_index = cPickle.load(open(\"./out/items_index.pkl\", 'rb'))\n",
    "\n",
    "n_users = len(users_index)\n",
    "n_items = len(items_index)\n",
    "    \n",
    "# 倒排表\n",
    "# 每个用户打过分的电影\n",
    "user_items = cPickle.load(open(\"./out/user_items.pkl\", 'rb'))\n",
    "# 对每个电影打过分的用户\n",
    "item_users = cPickle.load(open(\"./out/item_users.pkl\", 'rb'))\n",
    "\n",
    "# 用户-物品关系矩阵R\n",
    "user_item_scores = sio.mmread(\"./out/user_item_scores\")\n",
    "user_item_scores = user_item_scores.tocsr()\n",
    "\n",
    "users_mu = np.zeros(n_users)\n",
    "for u in range(n_users):\n",
    "    n_user_items = 0\n",
    "    r_acc = 0.0\n",
    "    \n",
    "    for i in user_items[u]:  # 用户打过分的item\n",
    "        r_acc += user_item_scores[u, i]\n",
    "        n_user_items += 1\n",
    "    \n",
    "    users_mu[u] = r_acc / n_user_items\n",
    "    \n",
    "def user_similarity(uid1, uid2):\n",
    "    \"\"\"\n",
    "    计算两个User的相似性\n",
    "    :param uid1: 1号User的index\n",
    "    :param uid2: 2号User的index\n",
    "    :return: 两个User的相似度\n",
    "    \"\"\"\n",
    "    si = {}\n",
    "    for item in user_items[uid1]:\n",
    "        if item in user_items[uid2]:\n",
    "            si[item] = 1\n",
    "        \n",
    "    n = len(si)\n",
    "    if n == 0:\n",
    "        similarity = 0.0  \n",
    "        return similarity\n",
    "\n",
    "    # 用户uid1的有效打分(减去该用户的平均打分)\n",
    "    s1 = np.array([user_item_scores[uid1, item] - users_mu[uid1] for item in si])\n",
    "    \n",
    "    # 用户uid2的有效打分(减去该用户的平均打分)\n",
    "    s2 = np.array([user_item_scores[uid2,item]-users_mu[uid2] for item in si])\n",
    "    \n",
    "    similarity = 1 - ssd.cosine(s1, s2) \n",
    "    \n",
    "    if np.isnan(similarity): # s1或s2的l2模为0（全部等于该用户的平均打分）\n",
    "        similarity = 0.0\n",
    "\n",
    "    return similarity\n",
    "    \n",
    "users_similarity_matrix = np.matrix(np.zeros(shape=(n_users, n_users)), float)\n",
    "\n",
    "print(\"n_users={}\\n\".format(n_users))\n",
    "time_start = time.time()\n",
    "\n",
    "total_elapsed_time = 0\n",
    "each_time_start = time_start\n",
    "for ui in range(n_users):\n",
    "    users_similarity_matrix[ui, ui] = 1.0\n",
    "    \n",
    "    if ui % 100 == 0:\n",
    "        time_tick = time.time()\n",
    "        elapsed_time = time_tick - each_time_start\n",
    "        total_elapsed_time += elapsed_time\n",
    "        each_time_start = time_tick\n",
    "        print(\"ui={}, cost_sec:{}, total_cost_sec:{}\".format(\n",
    "            ui, elapsed_time, total_elapsed_time))\n",
    "\n",
    "    for uj in range(ui + 1, n_users):\n",
    "        similarity = user_similarity(ui, uj)\n",
    "        users_similarity_matrix[uj, ui] = similarity\n",
    "        users_similarity_matrix[ui, uj] = similarity\n",
    "\n",
    "time_end = time.time()\n",
    "elapsed_time = time_end - time_start\n",
    "print(\"计算所有用户的相似性耗时:{:.4f}秒\".format(elapsed_time))\n",
    "\n",
    "cPickle.dump(users_similarity_matrix, open(\"./out/users_similarity.pkl\", 'wb'))\n",
    "```\n",
    "\n",
    "第一部分代码的输出为:\n",
    "\n",
    "```\n",
    "n_users=943\n",
    "\n",
    "ui=0, cost_sec:0.002000093460083008, total_cost_sec:0.002000093460083008\n",
    "ui=100, cost_sec:65.77476191520691, total_cost_sec:65.77676200866699\n",
    "ui=200, cost_sec:49.607837438583374, total_cost_sec:115.38459944725037\n",
    "ui=300, cost_sec:58.164326906204224, total_cost_sec:173.5489263534546\n",
    "ui=400, cost_sec:63.93165683746338, total_cost_sec:237.48058319091797\n",
    "ui=500, cost_sec:73.70421552658081, total_cost_sec:311.1847987174988\n",
    "ui=600, cost_sec:51.23693060874939, total_cost_sec:362.42172932624817\n",
    "ui=700, cost_sec:41.100350856781006, total_cost_sec:403.5220801830292\n",
    "ui=800, cost_sec:24.21438503265381, total_cost_sec:427.736465215683\n",
    "ui=900, cost_sec:13.202754974365234, total_cost_sec:440.9392201900482\n",
    "计算所有用户的相似性耗时:442.0673秒\n",
    "```\n",
    "\n",
    "第二部分代码为：\n",
    "\n",
    "```\n",
    "def user_cf_pred(user_idx, item_idx):\n",
    "    \"\"\"\n",
    "    预测User对Item的打分\n",
    "    :param user_idx: User的index\n",
    "    :param item_idx: Item的index\n",
    "    :return: User对Item的预测打分\n",
    "    \"\"\"\n",
    "    total_weighted_score = 0.0\n",
    "    total_sim = 0.0\n",
    "    \n",
    "    user_idxs = item_users[item_idx]\n",
    "    for each_user_idx in user_idxs:\n",
    "        if user_idx == each_user_idx:\n",
    "            continue\n",
    "        \n",
    "        each_sim = users_similarity_matrix[user_idx, each_user_idx]\n",
    "        if np.isnan(each_sim) or each_sim == 0:\n",
    "            continue\n",
    "        \n",
    "        each_score = user_item_scores[each_user_idx, item_idx]\n",
    "        each_score = each_score - users_mu[each_user_idx]\n",
    "        total_weighted_score = total_weighted_score + each_sim * each_score\n",
    "        \n",
    "        total_sim = total_sim + abs(each_sim)\n",
    "        \n",
    "    if abs(total_sim) < 1e-6:\n",
    "        return users_mu[user_idx]\n",
    "    else:\n",
    "        return total_weighted_score * 1.0 / total_sim\n",
    "        \n",
    "def recommend(user_id):\n",
    "    \"\"\"\n",
    "    返回推荐items及其打分（DataFrame）\n",
    "    :param user_id: User的userId\n",
    "    :return: 推荐结果列表\n",
    "    \"\"\"\n",
    "    cur_user_idx = users_index[user_id]\n",
    "    \n",
    "    # 训练集中该用户打过分的item\n",
    "    cur_user_item_idxs = user_items[cur_user_idx]\n",
    "\n",
    "    # 该用户对所有item的打分(注定是稀疏的)\n",
    "    cur_user_items_scores = np.zeros(n_items)\n",
    "    for each_item_idx in range(n_items):\n",
    "        if each_item_idx in cur_user_item_idxs:\n",
    "            continue\n",
    "        cur_user_items_scores[each_item_idx] = user_cf_pred(cur_user_idx,\n",
    "                                                            each_item_idx)\n",
    "    \n",
    "    # 推荐\n",
    "    item_score_list = [(e, i)\\\n",
    "                       for i, e in enumerate(list(cur_user_items_scores))]\n",
    "    sort_index = sorted(item_score_list, key=lambda x: x[0], reverse=True)\n",
    "    \n",
    "    columns = ['item_id', 'score']\n",
    "    df = pd.DataFrame(columns=columns)\n",
    "         \n",
    "    for each_score, each_item_idx in sort_index:\n",
    "        if np.isnan(each_score):\n",
    "            continue\n",
    "            \n",
    "        if each_item_idx in cur_user_item_idxs:\n",
    "            continue\n",
    "        \n",
    "        item_key_idx = list(items_index.values()).index(each_item_idx)\n",
    "        item_id = list(items_index.keys())[item_key_idx]\n",
    "        df.loc[len(df)] = [item_id, each_score]\n",
    "    \n",
    "    return df\n",
    "    \n",
    "# 读取测试数据\n",
    "triplet_cols = ['user_id', 'item_id', 'rating', 'timestamp'] \n",
    "\n",
    "dpath = './data/u1.test'\n",
    "df_triplet_test = pd.read_csv(dpath, \n",
    "                              sep='\\t', \n",
    "                              names=triplet_cols, \n",
    "                              encoding='latin-1')\n",
    "\n",
    "def recommend_users(user_ids):\n",
    "    \"\"\"\n",
    "    为指定一批User推荐Item, 并返回推荐结果\n",
    "    :param user_ids: userId列表\n",
    "    :return: \n",
    "    \"\"\"\n",
    "    userid_rec_results = dict()\n",
    "    \n",
    "    time_start = time.time()\n",
    "    each_time_start = time_start\n",
    "    count = 0\n",
    "    \n",
    "    print(\"开始对{}个User计算推荐结果\".format(len(user_ids)))\n",
    "    for user_id in user_ids:\n",
    "        count = count + 1\n",
    "        if user_id not in users_index:\n",
    "            print(\"{} is a new user.\".format(user_id))\n",
    "            continue\n",
    "        \n",
    "        each_rec_items = recommend(user_id)\n",
    "        userid_rec_results[user_id] = each_rec_items\n",
    "        \n",
    "        if count % 100 == 0:\n",
    "            each_time_tick = time.time()\n",
    "            each_cost_time = each_time_tick - each_time_start\n",
    "            each_time_start = each_time_tick\n",
    "            print(\"user_index:{}, each_cost_time:{}\".format(\n",
    "                    count - 1, each_cost_time))\n",
    "            \n",
    "    time_end = time.time()\n",
    "    total_cost_time = time_end - time_start\n",
    "    print(\"完成{}个User的推荐, 共计耗时{}秒\".format(\n",
    "        count, total_cost_time\n",
    "    ))\n",
    "        \n",
    "    return userid_rec_results\n",
    "    \n",
    "# 测试集中的user_id集合\n",
    "unique_users_test = df_triplet_test['user_id'].unique()\n",
    "total_rec_results = recommend_users(unique_users_test)\n",
    "\n",
    "```\n",
    "\n",
    "第二部分代码的输出为:\n",
    "\n",
    "```\n",
    "开始对459个User计算推荐结果\n",
    "user_index:99, each_cost_time:505.67792296409607\n",
    "user_index:199, each_cost_time:510.02417182922363\n",
    "user_index:299, each_cost_time:505.30590176582336\n",
    "user_index:399, each_cost_time:494.7492980957031\n",
    "完成459个User的推荐, 共计耗时2297.689420223236秒\n",
    "```\n",
    "\n",
    "第三部分代码为:\n",
    "\n",
    "```\n",
    "def evaluate(userid_rec_results, n_rec_items):\n",
    "    \"\"\"\n",
    "    为每个User截取若干条推荐结果，并衡量全体User的推荐效果\n",
    "    :param userid_rec_results:  推荐结果<userId -- 该user被推荐的全部Item>\n",
    "    :param n_rec_items:         每个所需截取的推荐结果的数量\n",
    "    :return: \n",
    "    \"\"\"\n",
    "    n_hits = 0              # TP\n",
    "    n_total_rec_items = 0   # TP+FP\n",
    "    n_total_test_items = 0  # TP+FN\n",
    "    all_rec_items = set()   # 所有User被推荐的Item的汇总\n",
    "    rss_test = 0.0          # 所有User的预测残差平方和\n",
    "\n",
    "    for user_id, rec_items in userid_rec_results.items():\n",
    "        user_records_test = df_triplet_test[df_triplet_test.user_id == user_id]\n",
    "        \n",
    "        # 累积TP和汇总所有User被推荐的指定数量的Item\n",
    "        for i in range(n_rec_items):\n",
    "            item_id = rec_items.iloc[i]['item_id']\n",
    "            if item_id in user_records_test['item_id'].values:\n",
    "                n_hits = n_hits + 1\n",
    "            all_rec_items.add(item_id)\n",
    "\n",
    "        # 累积预测评分残差平方和\n",
    "        for i in range(user_records_test.shape[0]):\n",
    "            item = user_records_test.iloc[i]['item_id']\n",
    "            score = user_records_test.iloc[i]['rating']\n",
    "            \n",
    "            df1 = rec_items[rec_items.item_id == item]\n",
    "            if df1.shape[0] == 0:\n",
    "                print(\"{} is a new item.\".format(item))\n",
    "                continue\n",
    "            \n",
    "            pred_score = df1['score'].values[0]\n",
    "            rss_test = rss_test + (pred_score - score)**2\n",
    "    \n",
    "        # 推荐的item总数(TP+FP)\n",
    "        n_total_rec_items = n_total_rec_items + n_rec_items\n",
    "    \n",
    "        # 真实item的总数(TP+FN)\n",
    "        n_total_test_items = n_total_test_items + user_records_test.shape[0]\n",
    "        \n",
    "    # Precision & Recall\n",
    "    precision = n_hits / (1.0 * n_total_rec_items)\n",
    "    recall = n_hits / (1.0 * n_total_test_items)\n",
    "    \n",
    "    # 覆盖度：推荐商品占总需要推荐商品的比例\n",
    "    coverage = len(all_rec_items) / (1.0 * n_items)\n",
    "    \n",
    "    # 打分的均方误差\n",
    "    rmse = np.sqrt(rss_test / df_triplet_test.shape[0])\n",
    "    \n",
    "    print(\"n_rec_items={}时:\\n \\tprecision={}\\n \"\n",
    "          \"\\trecall={}\\n \\tcoverage={}\\n \\trmse={}\".format(n_rec_items, \n",
    "                                                           precision, \n",
    "                                                           recall, \n",
    "                                                           coverage, \n",
    "                                                           rmse))\n",
    "                                                           \n",
    "# 分别计算推荐10个电影和20个电影时的precision/recall/coverage/rmse\n",
    "print(\"\\n推荐10个电影时的结果:\")\n",
    "evaluate(total_rec_results, 10)\n",
    "\n",
    "print(\"\\n\\n推荐20个电影时的结果\")\n",
    "evaluate(total_rec_results, 20)\n",
    "```\n",
    "\n",
    "第三部分代码的输出为:\n",
    "\n",
    "```\n",
    "推荐10个电影时的结果:\n",
    "599 is a new item.\n",
    "711 is a new item.\n",
    "814 is a new item.\n",
    "830 is a new item.\n",
    "852 is a new item.\n",
    "857 is a new item.\n",
    "1156 is a new item.\n",
    "1236 is a new item.\n",
    "1309 is a new item.\n",
    "1310 is a new item.\n",
    "1320 is a new item.\n",
    "1343 is a new item.\n",
    "1348 is a new item.\n",
    "1364 is a new item.\n",
    "1373 is a new item.\n",
    "1457 is a new item.\n",
    "1458 is a new item.\n",
    "1492 is a new item.\n",
    "1493 is a new item.\n",
    "1498 is a new item.\n",
    "1505 is a new item.\n",
    "1520 is a new item.\n",
    "1533 is a new item.\n",
    "1536 is a new item.\n",
    "1543 is a new item.\n",
    "1557 is a new item.\n",
    "1561 is a new item.\n",
    "1562 is a new item.\n",
    "1563 is a new item.\n",
    "1565 is a new item.\n",
    "1582 is a new item.\n",
    "1586 is a new item.\n",
    "n_rec_items=10时:\n",
    " \tprecision=0.0008714596949891067\n",
    " \trecall=0.0002\n",
    " \tcoverage=0.14606060606060606\n",
    " \trmse=3.6861559305022356\n",
    "\n",
    "\n",
    "推荐20个电影时的结果\n",
    "599 is a new item.\n",
    "711 is a new item.\n",
    "814 is a new item.\n",
    "830 is a new item.\n",
    "852 is a new item.\n",
    "857 is a new item.\n",
    "1156 is a new item.\n",
    "1236 is a new item.\n",
    "1309 is a new item.\n",
    "1310 is a new item.\n",
    "1320 is a new item.\n",
    "1343 is a new item.\n",
    "1348 is a new item.\n",
    "1364 is a new item.\n",
    "1373 is a new item.\n",
    "1457 is a new item.\n",
    "1458 is a new item.\n",
    "1492 is a new item.\n",
    "1493 is a new item.\n",
    "1498 is a new item.\n",
    "1505 is a new item.\n",
    "1520 is a new item.\n",
    "1533 is a new item.\n",
    "1536 is a new item.\n",
    "1543 is a new item.\n",
    "1557 is a new item.\n",
    "1561 is a new item.\n",
    "1562 is a new item.\n",
    "1563 is a new item.\n",
    "1565 is a new item.\n",
    "1582 is a new item.\n",
    "1586 is a new item.\n",
    "n_rec_items=20时:\n",
    " \tprecision=0.0017429193899782135\n",
    " \trecall=0.0008\n",
    " \tcoverage=0.22727272727272727\n",
    " \trmse=3.6861559305022356\n",
    "```\n",
    "\n",
    "+ 基于Item的CF\n",
    "第一部分代码如下:\n",
    "\n",
    "```\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "# load数据（用户和物品索引，以及倒排表）\n",
    "import _pickle as cPickle\n",
    "\n",
    "# 稀疏矩阵，打分表\n",
    "import scipy.io as sio\n",
    "import os\n",
    "\n",
    "# 距离\n",
    "import scipy.spatial.distance as ssd\n",
    "import time\n",
    "\n",
    "# 用户和item的索引\n",
    "users_index = cPickle.load(open(\"./out/users_index.pkl\", 'rb'))\n",
    "items_index = cPickle.load(open(\"./out/items_index.pkl\", 'rb'))\n",
    "\n",
    "n_users = len(users_index)\n",
    "n_items = len(items_index)\n",
    "    \n",
    "# 倒排表\n",
    "# 每个用户打过分的电影\n",
    "user_items = cPickle.load(open(\"./out/user_items.pkl\", 'rb'))\n",
    "# 对每个电影打过分的事用户\n",
    "item_users = cPickle.load(open(\"./out/item_users.pkl\", 'rb'))\n",
    "\n",
    "# 用户-物品关系矩阵R\n",
    "user_item_scores = sio.mmread(\"./out/user_item_scores\")\n",
    "user_item_scores = user_item_scores.tocsr()\n",
    "\n",
    "users_mu = np.zeros(n_users)\n",
    "for u in range(n_users):  \n",
    "    r_acc = 0.0\n",
    "    n_user_items = 0\n",
    "    \n",
    "    for i in user_items[u]:\n",
    "        # 用户打过分的item\n",
    "        r_acc += user_item_scores[u,i]\n",
    "        n_user_items += 1\n",
    "    \n",
    "    users_mu[u] = 1.0 * r_acc / n_user_items\n",
    "\n",
    "def item_similarity(iid1, iid2):\n",
    "    \"\"\"\n",
    "    根据对iid1和iid2都打过分的user, 来计算iid1和iid2的相似度\n",
    "    :param iid1: Item 1号\n",
    "    :param iid2: Item 2号\n",
    "    :return: [Item 1号] 和 [Item 2号] 的相似度\n",
    "    \"\"\"\n",
    "    \n",
    "    # 对iid1和iid2都打过分的user\n",
    "    su = {}\n",
    "    for user in item_users[iid1]:\n",
    "        if user in item_users[iid2]:\n",
    "            su[user] = 1\n",
    "        \n",
    "    n = len(su)\n",
    "    if n == 0:\n",
    "        similarity = 0  \n",
    "        return similarity  \n",
    "\n",
    "    # iid1的有效打分(减去用户的平均打分)\n",
    "    s1 = np.array([user_item_scores[user,iid1] - users_mu[user] for user in su])\n",
    "        \n",
    "    # iid2的有效打分(减去用户的平均打分)\n",
    "    s2 = np.array([user_item_scores[user,iid2] - users_mu[user] for user in su])  \n",
    "    \n",
    "    similarity = 1 - ssd.cosine(s1, s2) \n",
    "    if np.isnan(similarity):\n",
    "        similarity = 0.0\n",
    "    \n",
    "    return similarity\n",
    "    \n",
    "time_start = time.time()\n",
    "items_similarity_matrix = np.matrix(np.zeros(shape=(n_items, n_items)), float)\n",
    "\n",
    "print(\"开始计算{}个Item两两之间的相似度\".format(n_items))\n",
    "\n",
    "each_time_start = time_start\n",
    "for i in range(n_items):\n",
    "    items_similarity_matrix[i, i] = 1.0\n",
    "    \n",
    "    # 打印进度条\n",
    "    if i % 100 == 0:\n",
    "        each_time_tick = time.time()\n",
    "        each_cost_time = each_time_tick - each_time_start\n",
    "        each_time_start = time_start\n",
    "        print(\"处理到item_index={}, 耗时{:.4f}秒\".format(\n",
    "            i, each_cost_time\n",
    "        ))\n",
    "\n",
    "    for j in range(i + 1, n_items):\n",
    "        similarity = item_similarity(i, j)\n",
    "        items_similarity_matrix[i, j] = similarity\n",
    "        items_similarity_matrix[j, i] = similarity\n",
    "        \n",
    "cPickle.dump(items_similarity_matrix, open(\"./out/items_similarity.pkl\", 'wb')) \n",
    "\n",
    "time_end = time.time()\n",
    "total_cost_time = time_end - time_start\n",
    "print(\"计算{}个Item两两之间的相似度共计耗时{:.4f}秒\".format(\n",
    "    n_items, total_cost_time\n",
    "))\n",
    "\n",
    "print(\"Over!\")\n",
    "```\n",
    "\n",
    "第一部分代码的输出为:\n",
    "\n",
    "```\n",
    "开始计算1650个Item两两之间的相似度\n",
    "处理到item_index=0, 耗时0.0240秒\n",
    "D:\\Python37\\lib\\site-packages\\scipy\\spatial\\distance.py:720: RuntimeWarning: invalid value encountered in double_scalars\n",
    "  dist = 1.0 - uv / np.sqrt(uu * vv)\n",
    "处理到item_index=100, 耗时147.7364秒\n",
    "处理到item_index=200, 耗时258.5258秒\n",
    "处理到item_index=300, 耗时350.9221秒\n",
    "处理到item_index=400, 耗时423.8712秒\n",
    "处理到item_index=500, 耗时469.6529秒\n",
    "处理到item_index=600, 耗时509.7542秒\n",
    "处理到item_index=700, 耗时527.4572秒\n",
    "处理到item_index=800, 耗时545.2022秒\n",
    "处理到item_index=900, 耗时556.5208秒\n",
    "处理到item_index=1000, 耗时564.0233秒\n",
    "处理到item_index=1100, 耗时568.6915秒\n",
    "处理到item_index=1200, 耗时571.4437秒\n",
    "处理到item_index=1300, 耗时572.9158秒\n",
    "处理到item_index=1400, 耗时573.9998秒\n",
    "处理到item_index=1500, 耗时574.6429秒\n",
    "处理到item_index=1600, 耗时574.8949秒\n",
    "计算1650个Item两两之间的相似度共计耗时575.1729秒\n",
    "Over!\n",
    "```\n",
    "\n",
    "第二部分的代码为:\n",
    "\n",
    "```\n",
    "def Item_CF_pred2(uid, iid, n_Knns): \n",
    "    \"\"\"\n",
    "    根据User打过分的Item中, 与目标Item最相似的若干个Item,\n",
    "    来预测User对目标Item的打分\n",
    "    :param uid: 目标User\n",
    "    :param iid: 目标Item的index\n",
    "    :param n_Knns: 所参考的其他Item的个数\n",
    "    :return: User对目标Item的打分\n",
    "    \"\"\"\n",
    "    \n",
    "    # 目标Item与所有其他Item的相似度\n",
    "    cur_items_similarity = np.array(items_similarity_matrix[iid, :]).flatten()\n",
    "    cur_items_similarity = list(cur_items_similarity)\n",
    "    sim_index_list = [(e, i) for i, e in enumerate(cur_items_similarity)]\n",
    "    sorted_sim_index_list = sorted(sim_index_list, reverse=True)\n",
    "    \n",
    "    # 对于所参考的其他Item, 累积其与目标Item的相似度加权和\n",
    "    weighted_total_sim = 0.0\n",
    "    # 对于所参考的其他Item, 累积其与目标Item的相似度之和\n",
    "    total_sim = 0.0\n",
    "    # 对于所参考的其他Item, 累积其个数\n",
    "    top_n_items = 0\n",
    "    \n",
    "    for each_item_sim, each_item_index in sorted_sim_index_list:\n",
    "        if each_item_index not in user_items[uid]:\n",
    "            continue\n",
    "\n",
    "        if each_item_sim != 0:\n",
    "            each_item_score = user_item_scores[uid, each_item_index]\n",
    "            weighted_total_sim += each_item_sim * each_item_score\n",
    "            total_sim += np.abs(each_item_sim)  \n",
    "        \n",
    "        top_n_items += 1\n",
    "        if top_n_items >= n_Knns:\n",
    "            break\n",
    "        \n",
    "    if total_sim != 0:  \n",
    "        score = weighted_total_sim / total_sim\n",
    "    else:\n",
    "        score = users_mu[uid]\n",
    "    \n",
    "    if score < 0:\n",
    "        score = 0.0\n",
    "    \n",
    "    return score\n",
    "    \n",
    "def recommend(user):\n",
    "    \"\"\"\n",
    "    返回推荐给User的Item列表和打分信息\n",
    "    :param user:        目标User的userId\n",
    "    :return:    推荐结果列表 \n",
    "    \"\"\"\n",
    "    \n",
    "    cur_user_index = users_index[user]\n",
    "    cur_user_items = user_items[cur_user_index]\n",
    "    user_items_scores = np.zeros(n_items)\n",
    "\n",
    "    for each_item_index in range(n_items): \n",
    "        if each_item_index not in cur_user_items:\n",
    "            user_items_scores[each_item_index] = Item_CF_pred2(cur_user_index, \n",
    "                                                               each_item_index, \n",
    "                                                               10)\n",
    "    \n",
    "    score_index_list = [(e, i) for i, e in enumerate(list(user_items_scores))]\n",
    "    sorted_score_index_list = sorted(score_index_list, reverse=True)\n",
    "    \n",
    "    columns = ['item_id', 'score']\n",
    "    df = pd.DataFrame(columns=columns)\n",
    "    \n",
    "    for each_score, each_item_index in sorted_score_index_list:\n",
    "        if np.isnan(each_score):\n",
    "            continue\n",
    "        \n",
    "        if each_item_index in cur_user_items:\n",
    "            continue\n",
    "        \n",
    "        # 根据value值(Item.index)寻找key值(Item.id)\n",
    "        each_item_key_index = list(items_index.values()).index(each_item_index)\n",
    "        each_item_id = list(items_index.keys())[each_item_key_index]\n",
    "        df.loc[len(df)] = [each_item_id, each_score]\n",
    "\n",
    "    return df\n",
    "    \n",
    "triplet_cols = ['user_id', 'item_id', 'rating', 'timestamp'] \n",
    "\n",
    "test_data_path = './data/u1.test'\n",
    "df_triplet_test = pd.read_csv(test_data_path, \n",
    "                              sep='\\t', \n",
    "                              names=triplet_cols, \n",
    "                              encoding='latin-1')\n",
    "                              \n",
    "def recommend_users(user_ids):\n",
    "    \"\"\"\n",
    "    为指定一批User推荐Item, 并返回推荐结果\n",
    "    :param user_ids: userId列表\n",
    "    :return: \n",
    "    \"\"\"\n",
    "    userid_rec_results = dict()\n",
    "    \n",
    "    time_start = time.time()\n",
    "    each_time_start = time_start\n",
    "    count = 0\n",
    "    \n",
    "    print(\"开始对{}个User计算推荐结果\".format(len(user_ids)))\n",
    "    for user_id in user_ids:\n",
    "        count = count + 1\n",
    "        if user_id not in users_index:\n",
    "            print(\"{} is a new user.\".format(user_id))\n",
    "            continue\n",
    "        \n",
    "        each_rec_items = recommend(user_id)\n",
    "        userid_rec_results[user_id] = each_rec_items\n",
    "        \n",
    "        if count % 100 == 0:\n",
    "            each_time_tick = time.time()\n",
    "            each_cost_time = each_time_tick - each_time_start\n",
    "            each_time_start = each_time_tick\n",
    "            print(\"user_index:{}, each_cost_time:{}\".format(\n",
    "                    count - 1, each_cost_time))\n",
    "            \n",
    "    time_end = time.time()\n",
    "    total_cost_time = time_end - time_start\n",
    "    print(\"完成{}个User的推荐, 共计耗时{}秒\".format(\n",
    "        count, total_cost_time\n",
    "    ))\n",
    "        \n",
    "    return userid_rec_results\n",
    "    \n",
    "# 测试集中的user_id集合\n",
    "unique_users_test = df_triplet_test['user_id'].unique()\n",
    "total_rec_results = recommend_users(unique_users_test)\n",
    "```\n",
    "\n",
    "第二部分代码的输出为:\n",
    "\n",
    "```\n",
    "开始对459个User计算推荐结果\n",
    "user_index:99, each_cost_time:476.13823342323303\n",
    "user_index:199, each_cost_time:479.92145013809204\n",
    "user_index:299, each_cost_time:479.76344084739685\n",
    "user_index:399, each_cost_time:469.2458393573761\n",
    "完成459个User的推荐, 共计耗时2173.505317211151秒\n",
    "```\n",
    "\n",
    "第三部分的代码为:\n",
    "\n",
    "```\n",
    "def evaluate(userid_rec_results, n_rec_items):\n",
    "    \"\"\"\n",
    "    为每个User截取若干条推荐结果，并衡量全体User的推荐效果\n",
    "    :param userid_rec_results:  推荐结果<userId -- 该user被推荐的全部Item>\n",
    "    :param n_rec_items:         每个所需截取的推荐结果的数量\n",
    "    :return: \n",
    "    \"\"\"\n",
    "    n_hits = 0              # TP\n",
    "    n_total_rec_items = 0   # TP+FP\n",
    "    n_total_test_items = 0  # TP+FN\n",
    "    all_rec_items = set()   # 所有User被推荐的Item的汇总\n",
    "    rss_test = 0.0          # 所有User的预测残差平方和\n",
    "\n",
    "    for user_id, rec_items in userid_rec_results.items():\n",
    "        user_records_test = df_triplet_test[df_triplet_test.user_id == user_id]\n",
    "        \n",
    "        # 累积TP和汇总所有User被推荐的指定数量的Item\n",
    "        for i in range(n_rec_items):\n",
    "            item_id = rec_items.iloc[i]['item_id']\n",
    "            if item_id in user_records_test['item_id'].values:\n",
    "                n_hits = n_hits + 1\n",
    "            all_rec_items.add(item_id)\n",
    "\n",
    "        # 累积预测评分残差平方和\n",
    "        for i in range(user_records_test.shape[0]):\n",
    "            item = user_records_test.iloc[i]['item_id']\n",
    "            score = user_records_test.iloc[i]['rating']\n",
    "            \n",
    "            df1 = rec_items[rec_items.item_id == item]\n",
    "            if df1.shape[0] == 0:\n",
    "                print(\"{} is a new item.\".format(item))\n",
    "                continue\n",
    "            \n",
    "            pred_score = df1['score'].values[0]\n",
    "            rss_test = rss_test + (pred_score - score)**2\n",
    "    \n",
    "        # 推荐的item总数(TP+FP)\n",
    "        n_total_rec_items = n_total_rec_items + n_rec_items\n",
    "    \n",
    "        # 真实item的总数(TP+FN)\n",
    "        n_total_test_items = n_total_test_items + user_records_test.shape[0]\n",
    "        \n",
    "    # Precision & Recall\n",
    "    precision = n_hits / (1.0 * n_total_rec_items)\n",
    "    recall = n_hits / (1.0 * n_total_test_items)\n",
    "    \n",
    "    # 覆盖度：推荐商品占总需要推荐商品的比例\n",
    "    coverage = len(all_rec_items) / (1.0 * n_items)\n",
    "    \n",
    "    # 打分的均方误差\n",
    "    rmse = np.sqrt(rss_test / df_triplet_test.shape[0])\n",
    "    \n",
    "    print(\"n_rec_items={}时:\\n \\tprecision={}\\n \"\n",
    "          \"\\trecall={}\\n \\tcoverage={}\\n \\trmse={}\".format(n_rec_items, \n",
    "                                                           precision, \n",
    "                                                           recall, \n",
    "                                                           coverage, \n",
    "                                                           rmse))\n",
    "                                                           \n",
    "# 分别计算推荐10个电影和20个电影时的precision/recall/coverage/rmse\n",
    "print(\"\\n推荐10个电影时的结果:\")\n",
    "evaluate(total_rec_results, 10)\n",
    "\n",
    "print(\"\\n\\n推荐20个电影时的结果\")\n",
    "evaluate(total_rec_results, 20)\n",
    "```\n",
    "\n",
    "第三部分代码的输出为:\n",
    "\n",
    "```\n",
    "推荐10个电影时的结果:\n",
    "599 is a new item.\n",
    "711 is a new item.\n",
    "814 is a new item.\n",
    "830 is a new item.\n",
    "852 is a new item.\n",
    "857 is a new item.\n",
    "1156 is a new item.\n",
    "1236 is a new item.\n",
    "1309 is a new item.\n",
    "1310 is a new item.\n",
    "1320 is a new item.\n",
    "1343 is a new item.\n",
    "1348 is a new item.\n",
    "1364 is a new item.\n",
    "1373 is a new item.\n",
    "1457 is a new item.\n",
    "1458 is a new item.\n",
    "1492 is a new item.\n",
    "1493 is a new item.\n",
    "1498 is a new item.\n",
    "1505 is a new item.\n",
    "1520 is a new item.\n",
    "1533 is a new item.\n",
    "1536 is a new item.\n",
    "1543 is a new item.\n",
    "1557 is a new item.\n",
    "1561 is a new item.\n",
    "1562 is a new item.\n",
    "1563 is a new item.\n",
    "1565 is a new item.\n",
    "1582 is a new item.\n",
    "1586 is a new item.\n",
    "n_rec_items=10时:\n",
    " \tprecision=0.06274509803921569\n",
    " \trecall=0.0144\n",
    " \tcoverage=0.48727272727272725\n",
    " \trmse=1.1327763491486122\n",
    "\n",
    "\n",
    "推荐20个电影时的结果\n",
    "599 is a new item.\n",
    "711 is a new item.\n",
    "814 is a new item.\n",
    "830 is a new item.\n",
    "852 is a new item.\n",
    "857 is a new item.\n",
    "1156 is a new item.\n",
    "1236 is a new item.\n",
    "1309 is a new item.\n",
    "1310 is a new item.\n",
    "1320 is a new item.\n",
    "1343 is a new item.\n",
    "1348 is a new item.\n",
    "1364 is a new item.\n",
    "1373 is a new item.\n",
    "1457 is a new item.\n",
    "1458 is a new item.\n",
    "1492 is a new item.\n",
    "1493 is a new item.\n",
    "1498 is a new item.\n",
    "1505 is a new item.\n",
    "1520 is a new item.\n",
    "1533 is a new item.\n",
    "1536 is a new item.\n",
    "1543 is a new item.\n",
    "1557 is a new item.\n",
    "1561 is a new item.\n",
    "1562 is a new item.\n",
    "1563 is a new item.\n",
    "1565 is a new item.\n",
    "1582 is a new item.\n",
    "1586 is a new item.\n",
    "n_rec_items=20时:\n",
    " \tprecision=0.0659041394335512\n",
    " \trecall=0.03025\n",
    " \tcoverage=0.7260606060606061\n",
    " \trmse=1.1327763491486122\n",
    "```\n",
    "\n",
    "+ 基于矩阵分解的CF\n",
    "第一部分代码为:\n",
    "\n",
    "```\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "# load数据（用户和物品索引，以及倒排表）\n",
    "import _pickle as cPickle\n",
    "import json\n",
    "\n",
    "from numpy.random import random\n",
    "\n",
    "# 用户和item的索引\n",
    "users_index = cPickle.load(open(\"./out/users_index.pkl\", 'rb'))\n",
    "items_index = cPickle.load(open(\"./out/items_index.pkl\", 'rb'))\n",
    "\n",
    "n_users = len(users_index)\n",
    "n_items = len(items_index)\n",
    "    \n",
    "# 倒排表\n",
    "# 每个用户打过分的电影\n",
    "user_items = cPickle.load(open(\"./out/user_items.pkl\", 'rb'))\n",
    "# 对每个电影打过分的事用户\n",
    "item_users = cPickle.load(open(\"./out/item_users.pkl\", 'rb'))\n",
    "\n",
    "# 读取训练数据\n",
    "triplet_cols = ['user_id','item_id', 'rating', 'timestamp'] \n",
    "\n",
    "dpath = './data/u1.base'\n",
    "df_triplet = pd.read_csv(dpath, \n",
    "                         sep='\\t', \n",
    "                         names=triplet_cols, \n",
    "                         encoding='latin-1')\n",
    "df_triplet = df_triplet.drop(['timestamp'], axis=1)\n",
    "\n",
    "# 隐含变量的维数\n",
    "K = 40\n",
    "\n",
    "# r(ui) = \\mu + bu + bi + Pu'T Qi\n",
    "\n",
    "# Item和User的偏置项\n",
    "bi = np.zeros((n_items, 1))\n",
    "bu = np.zeros((n_users, 1))\n",
    "\n",
    "# Item和User的隐含向量\n",
    "qi = np.zeros((n_items, K))    \n",
    "pu = np.zeros((n_users, K))   \n",
    "\n",
    "for uid in range(n_users):\n",
    "    pu[uid] = np.reshape(random((K, 1)) / 10 * np.sqrt(K), K)\n",
    "       \n",
    "for iid in range(n_items):\n",
    "    qi[iid] = np.reshape(random((K, 1)) / 10 * np.sqrt(K), K)\n",
    "\n",
    "# 所有用户的平均打分\n",
    "mu = df_triplet['rating'].mean()\n",
    "\n",
    "def svd_pred(uid, iid):  \n",
    "    score = mu + bi[iid] + bu[uid] + np.sum(qi[iid] * pu[uid]) \n",
    "    return score\n",
    "    \n",
    "# gamma：为学习率\n",
    "# Lambda：正则参数\n",
    "# steps：迭代次数\n",
    "import time\n",
    "\n",
    "steps = 50\n",
    "gamma = 0.04\n",
    "Lambda = 0.15\n",
    "\n",
    "# 总的打分记录数目\n",
    "n_records = df_triplet.shape[0]\n",
    "\n",
    "time_start = time.time()\n",
    "\n",
    "print(\"开始进行{}个step的训练\".format(steps))\n",
    "\n",
    "each_time_start = time_start\n",
    "for step in range(steps):\n",
    "    print('The {}-th  step is running'.format(step))\n",
    "    rmse_sum = 0.0\n",
    "            \n",
    "    # 将训练样本打散顺序\n",
    "    kk = np.random.permutation(n_records)  \n",
    "    for j in range(n_records):\n",
    "        # 每次一个训练样本\n",
    "        line = kk[j]\n",
    "        \n",
    "        uid = users_index[df_triplet.iloc[line]['user_id']]\n",
    "        iid = items_index[df_triplet.iloc[line]['item_id']]\n",
    "        rating = df_triplet.iloc[line]['rating']\n",
    "\n",
    "        # 预测残差\n",
    "        eui = rating - svd_pred(uid, iid)\n",
    "        # 残差平方和\n",
    "        rmse_sum += eui**2\n",
    "\n",
    "        # 随机梯度下降，更新\n",
    "        bu[uid] += gamma * (eui - Lambda * bu[uid])  \n",
    "        bi[iid] += gamma * (eui - Lambda * bi[iid])\n",
    "                \n",
    "        temp = qi[iid]  \n",
    "        qi[iid] += gamma * (eui * pu[uid] - Lambda * qi[iid])\n",
    "        pu[uid] += gamma * (eui * temp - Lambda * pu[uid])\n",
    "            \n",
    "    # 学习率递减\n",
    "    gamma = gamma * 0.93\n",
    "    each_rmse = np.sqrt(rmse_sum / n_records)\n",
    "    \n",
    "    each_time_tick = time.time()\n",
    "    each_cost_time = each_time_tick - each_time_start\n",
    "    each_time_start = each_time_tick\n",
    "\n",
    "    print(\"完成第{}个step的训练, rmse={}, 耗时{:.4f}秒\".format(\n",
    "        step + 1, each_rmse, each_cost_time))\n",
    "\n",
    "time_end = time.time()\n",
    "total_cost_time = time_end - time_start\n",
    "print(\"结束了{}个step的训练，总耗时{:.4f}秒\".format(steps, total_cost_time))\n",
    "```\n",
    "\n",
    "第一部分代码的输出结果为:\n",
    "\n",
    "```\n",
    "开始进行50个step的训练\n",
    "The 0-th  step is running\n",
    "完成第1个step的训练, rmse=[1.18058585], 耗时41.8464秒\n",
    "The 1-th  step is running\n",
    "完成第2个step的训练, rmse=[0.9270805], 耗时41.7024秒\n",
    "The 2-th  step is running\n",
    "完成第3个step的训练, rmse=[0.90726438], 耗时41.5924秒\n",
    "The 3-th  step is running\n",
    "完成第4个step的训练, rmse=[0.89555945], 耗时41.7614秒\n",
    "The 4-th  step is running\n",
    "完成第5个step的训练, rmse=[0.88663799], 耗时41.5904秒\n",
    "The 5-th  step is running\n",
    "完成第6个step的训练, rmse=[0.87725411], 耗时41.6154秒\n",
    "The 6-th  step is running\n",
    "完成第7个step的训练, rmse=[0.87025475], 耗时41.7684秒\n",
    "The 7-th  step is running\n",
    "完成第8个step的训练, rmse=[0.86404012], 耗时41.5764秒\n",
    "The 8-th  step is running\n",
    "完成第9个step的训练, rmse=[0.85778955], 耗时41.6064秒\n",
    "The 9-th  step is running\n",
    "完成第10个step的训练, rmse=[0.85265384], 耗时41.4864秒\n",
    "The 10-th  step is running\n",
    "完成第11个step的训练, rmse=[0.84856777], 耗时41.6094秒\n",
    "The 11-th  step is running\n",
    "完成第12个step的训练, rmse=[0.84451892], 耗时41.6154秒\n",
    "The 12-th  step is running\n",
    "完成第13个step的训练, rmse=[0.84105291], 耗时41.8264秒\n",
    "The 13-th  step is running\n",
    "完成第14个step的训练, rmse=[0.83839413], 耗时41.9524秒\n",
    "The 14-th  step is running\n",
    "完成第15个step的训练, rmse=[0.83543897], 耗时41.5984秒\n",
    "The 15-th  step is running\n",
    "完成第16个step的训练, rmse=[0.83309249], 耗时41.9204秒\n",
    "The 16-th  step is running\n",
    "完成第17个step的训练, rmse=[0.83090809], 耗时41.6524秒\n",
    "The 17-th  step is running\n",
    "完成第18个step的训练, rmse=[0.82885146], 耗时41.6834秒\n",
    "The 18-th  step is running\n",
    "完成第19个step的训练, rmse=[0.82715086], 耗时41.8244秒\n",
    "The 19-th  step is running\n",
    "完成第20个step的训练, rmse=[0.82529596], 耗时41.7094秒\n",
    "The 20-th  step is running\n",
    "完成第21个step的训练, rmse=[0.8239932], 耗时41.6104秒\n",
    "The 21-th  step is running\n",
    "完成第22个step的训练, rmse=[0.82256499], 耗时41.7044秒\n",
    "The 22-th  step is running\n",
    "完成第23个step的训练, rmse=[0.82124946], 耗时41.7554秒\n",
    "The 23-th  step is running\n",
    "完成第24个step的训练, rmse=[0.82003843], 耗时41.7624秒\n",
    "The 24-th  step is running\n",
    "完成第25个step的训练, rmse=[0.81899814], 耗时41.8984秒\n",
    "The 25-th  step is running\n",
    "完成第26个step的训练, rmse=[0.81793132], 耗时41.7614秒\n",
    "The 26-th  step is running\n",
    "完成第27个step的训练, rmse=[0.81715274], 耗时41.8804秒\n",
    "The 27-th  step is running\n",
    "完成第28个step的训练, rmse=[0.8162825], 耗时41.7094秒\n",
    "The 28-th  step is running\n",
    "完成第29个step的训练, rmse=[0.81544997], 耗时41.8024秒\n",
    "The 29-th  step is running\n",
    "完成第30个step的训练, rmse=[0.81473627], 耗时41.7464秒\n",
    "The 30-th  step is running\n",
    "完成第31个step的训练, rmse=[0.81419161], 耗时41.5944秒\n",
    "The 31-th  step is running\n",
    "完成第32个step的训练, rmse=[0.81347666], 耗时41.7294秒\n",
    "The 32-th  step is running\n",
    "完成第33个step的训练, rmse=[0.81287154], 耗时41.4564秒\n",
    "The 33-th  step is running\n",
    "完成第34个step的训练, rmse=[0.81232654], 耗时41.5754秒\n",
    "The 34-th  step is running\n",
    "完成第35个step的训练, rmse=[0.81191833], 耗时41.5164秒\n",
    "The 35-th  step is running\n",
    "完成第36个step的训练, rmse=[0.81144414], 耗时41.5674秒\n",
    "The 36-th  step is running\n",
    "完成第37个step的训练, rmse=[0.81100497], 耗时41.8414秒\n",
    "The 37-th  step is running\n",
    "完成第38个step的训练, rmse=[0.81069703], 耗时41.8644秒\n",
    "The 38-th  step is running\n",
    "完成第39个step的训练, rmse=[0.81026707], 耗时41.6944秒\n",
    "The 39-th  step is running\n",
    "完成第40个step的训练, rmse=[0.80993264], 耗时41.6474秒\n",
    "The 40-th  step is running\n",
    "完成第41个step的训练, rmse=[0.80959347], 耗时41.6014秒\n",
    "The 41-th  step is running\n",
    "完成第42个step的训练, rmse=[0.8093159], 耗时41.6124秒\n",
    "The 42-th  step is running\n",
    "完成第43个step的训练, rmse=[0.80910571], 耗时41.6074秒\n",
    "The 43-th  step is running\n",
    "完成第44个step的训练, rmse=[0.80879311], 耗时41.7154秒\n",
    "The 44-th  step is running\n",
    "完成第45个step的训练, rmse=[0.80862828], 耗时41.8024秒\n",
    "The 45-th  step is running\n",
    "完成第46个step的训练, rmse=[0.80837109], 耗时41.6534秒\n",
    "The 46-th  step is running\n",
    "完成第47个step的训练, rmse=[0.80819926], 耗时41.6784秒\n",
    "The 47-th  step is running\n",
    "完成第48个step的训练, rmse=[0.808019], 耗时41.7974秒\n",
    "The 48-th  step is running\n",
    "完成第49个step的训练, rmse=[0.80779787], 耗时41.5034秒\n",
    "The 49-th  step is running\n",
    "完成第50个step的训练, rmse=[0.80766296], 耗时41.7224秒\n",
    "结束了50个step的训练，总耗时2084.7492秒\n",
    "```\n",
    "\n",
    "第二部分的代码为:\n",
    "\n",
    "```\n",
    "# A method for saving object data to JSON file\n",
    "def save_json(filepath):\n",
    "    dict_ = dict()\n",
    "    dict_['mu'] = mu\n",
    "    dict_['K'] = K\n",
    "    \n",
    "    dict_['bi'] = bi.tolist()\n",
    "    dict_['bu'] = bu.tolist()\n",
    "    \n",
    "    dict_['qi'] = qi.tolist()\n",
    "    dict_['pu'] = pu.tolist()\n",
    "\n",
    "    # Creat json and save to file\n",
    "    json_txt = json.dumps(dict_)\n",
    "    with open(filepath, 'w') as file:\n",
    "        file.write(json_txt)\n",
    "        \n",
    "# A method for loading data from JSON file\n",
    "def load_json(filepath):\n",
    "    with open(filepath, 'r') as file:\n",
    "        dict_ = json.load(file)\n",
    "\n",
    "        mu = dict_['mu']\n",
    "        K = dict_['K']\n",
    "\n",
    "        bi = np.asarray(dict_['bi'])\n",
    "        bu = np.asarray(dict_['bu'])\n",
    "    \n",
    "        qi = np.asarray(dict_['qi'])\n",
    "        pu = np.asarray(dict_['pu'])\n",
    "        \n",
    "        \n",
    "save_json('./out/svd_model.json')\n",
    "load_json('./out/svd_model.json')\n",
    "\n",
    "def recommend(user):\n",
    "    \"\"\"\n",
    "    返回推荐items及其打分（DataFrame）\n",
    "    :param user: 输出User的userId\n",
    "    :return: 推荐结果DataFrame, 包含item_id和score\n",
    "    \"\"\"\n",
    "    cur_user_id = users_index[user]\n",
    "    \n",
    "    # 训练集中该用户打过分的item\n",
    "    cur_user_items = user_items[cur_user_id]\n",
    "\n",
    "    # 该用户对所有item的打分\n",
    "    user_items_scores = np.zeros(n_items)\n",
    "\n",
    "    # 预测打分\n",
    "    for i in range(n_items):\n",
    "        if i not in cur_user_items:\n",
    "            user_items_scores[i] = svd_pred(cur_user_id, i)\n",
    "    \n",
    "    # 推荐\n",
    "    sort_list = [(e, i) for i, e in enumerate(list(user_items_scores))]\n",
    "    sort_index = sorted(sort_list, reverse=True)\n",
    "    \n",
    "    # 创建DataFrame, 返回推荐列表\n",
    "    columns = ['item_id', 'score']\n",
    "    df = pd.DataFrame(columns=columns)\n",
    "\n",
    "    for each_item_score, each_item_index in sort_index:\n",
    "        if np.isnan(each_item_score):\n",
    "            continue\n",
    "        \n",
    "        if each_item_index in cur_user_items:\n",
    "            continue\n",
    "        \n",
    "        each_item_key_index = list(items_index.values()).index(each_item_index)\n",
    "        each_item_id = list(items_index.keys())[each_item_key_index]\n",
    "        df.loc[len(df)] = [each_item_id, each_item_score]\n",
    "    \n",
    "    return df\n",
    "    \n",
    "# 读取测试数据\n",
    "triplet_cols = ['user_id', 'item_id', 'rating', 'timestamp'] \n",
    "\n",
    "dpath = './data/u1.test'\n",
    "df_triplet_test = pd.read_csv(dpath,\n",
    "                              sep='\\t', \n",
    "                              names=triplet_cols, \n",
    "                              encoding='latin-1')\n",
    "                              \n",
    "def recommend_users(user_ids):\n",
    "    \"\"\"\n",
    "    为指定一批User推荐Item, 并返回推荐结果\n",
    "    :param user_ids: userId列表\n",
    "    :return: \n",
    "    \"\"\"\n",
    "    userid_rec_results = dict()\n",
    "    \n",
    "    time_start = time.time()\n",
    "    each_time_start = time_start\n",
    "    count = 0\n",
    "    \n",
    "    print(\"开始对{}个User计算推荐结果\".format(len(user_ids)))\n",
    "    for user_id in user_ids:\n",
    "        count = count + 1\n",
    "        if user_id not in users_index:\n",
    "            print(\"{} is a new user.\".format(user_id))\n",
    "            continue\n",
    "        \n",
    "        each_rec_items = recommend(user_id)\n",
    "        userid_rec_results[user_id] = each_rec_items\n",
    "        \n",
    "        if count % 100 == 0:\n",
    "            each_time_tick = time.time()\n",
    "            each_cost_time = each_time_tick - each_time_start\n",
    "            each_time_start = each_time_tick\n",
    "            print(\"user_index:{}, each_cost_time:{}\".format(\n",
    "                    count - 1, each_cost_time))\n",
    "            \n",
    "    time_end = time.time()\n",
    "    total_cost_time = time_end - time_start\n",
    "    print(\"完成{}个User的推荐, 共计耗时{}秒\".format(\n",
    "        count, total_cost_time\n",
    "    ))\n",
    "\n",
    "    return userid_rec_results\n",
    "    \n",
    "# 测试集中的user_id集合\n",
    "unique_users_test = df_triplet_test['user_id'].unique()\n",
    "total_rec_results = recommend_users(unique_users_test)\n",
    "```\n",
    "\n",
    "第二部分代码的输出结果为:\n",
    "\n",
    "```\n",
    "开始对459个User计算推荐结果\n",
    "user_index:99, each_cost_time:197.35128784179688\n",
    "user_index:199, each_cost_time:198.34334468841553\n",
    "user_index:299, each_cost_time:195.94120740890503\n",
    "user_index:399, each_cost_time:193.48006629943848\n",
    "完成459个User的推荐, 共计耗时896.7402906417847秒\n",
    "```\n",
    "\n",
    "第三部分的代码为:\n",
    "\n",
    "```\n",
    "def evaluate(userid_rec_results, n_rec_items):\n",
    "    \"\"\"\n",
    "    为每个User截取若干条推荐结果，并衡量全体User的推荐效果\n",
    "    :param userid_rec_results:  推荐结果<userId -- 该user被推荐的全部Item>\n",
    "    :param n_rec_items:         每个所需截取的推荐结果的数量\n",
    "    :return: \n",
    "    \"\"\"\n",
    "    n_hits = 0            # TP\n",
    "    n_total_rec_items = 0    # TP+FP\n",
    "    n_total_test_items = 0   # TP+FN\n",
    "    all_rec_items = set()    # 所有User被推荐的Item的汇总\n",
    "    rss_test = 0.0         # 所有User的预测残差平方和\n",
    "\n",
    "    for user_id, rec_items in userid_rec_results.items():\n",
    "        user_records_test = df_triplet_test[df_triplet_test.user_id == user_id]\n",
    "        \n",
    "        # 累积TP和汇总所有User被推荐的指定数量的Item\n",
    "        for i in range(n_rec_items):\n",
    "            item_id = rec_items.iloc[i]['item_id']\n",
    "            if item_id in user_records_test['item_id'].values:\n",
    "                n_hits = n_hits + 1\n",
    "            all_rec_items.add(item_id)\n",
    "\n",
    "        # 累积预测评分残差平方和\n",
    "        for i in range(user_records_test.shape[0]):\n",
    "            item = user_records_test.iloc[i]['item_id']\n",
    "            score = user_records_test.iloc[i]['rating']\n",
    "            \n",
    "            df1 = rec_items[rec_items.item_id == item]\n",
    "            if df1.shape[0] == 0:\n",
    "                print(\"{} is a new item.\".format(item))\n",
    "                continue\n",
    "            \n",
    "            pred_score = df1['score'].values[0]\n",
    "            rss_test = rss_test + (pred_score - score)**2\n",
    "    \n",
    "        # 推荐的item总数(TP+FP)\n",
    "        n_total_rec_items = n_total_rec_items + n_rec_items\n",
    "    \n",
    "        # 真实item的总数(TP+FN)\n",
    "        n_total_test_items = n_total_test_items + user_records_test.shape[0]\n",
    "        \n",
    "    # Precision & Recall\n",
    "    precision = n_hits / (1.0 * n_total_rec_items)\n",
    "    recall = n_hits / (1.0 * n_total_test_items)\n",
    "    \n",
    "    # 覆盖度：推荐商品占总需要推荐商品的比例\n",
    "    coverage = len(all_rec_items) / (1.0 * n_items)\n",
    "    \n",
    "    # 打分的均方误差\n",
    "    rmse = np.sqrt(rss_test / df_triplet_test.shape[0])\n",
    "    \n",
    "    print(\"n_rec_items={}时:\\n \\tprecision={}\\n \"\n",
    "          \"\\trecall={}\\n \\tcoverage={}\\n \\trmse={}\".format(n_rec_items, \n",
    "                                                           precision, \n",
    "                                                           recall, \n",
    "                                                           coverage, \n",
    "                                                           rmse))\n",
    "                                                           \n",
    "# 分别计算推荐10个电影和20个电影时的precision/recall/coverage/rmse\n",
    "print(\"\\n推荐10个电影时的结果:\")\n",
    "evaluate(total_rec_results, 10)\n",
    "\n",
    "print(\"\\n\\n推荐20个电影时的结果\")\n",
    "evaluate(total_rec_results, 20)\n",
    "```\n",
    "\n",
    "第三部分代码的输出结果为:\n",
    "\n",
    "```\n",
    "推荐10个电影时的结果:\n",
    "599 is a new item.\n",
    "711 is a new item.\n",
    "814 is a new item.\n",
    "830 is a new item.\n",
    "852 is a new item.\n",
    "857 is a new item.\n",
    "1156 is a new item.\n",
    "1236 is a new item.\n",
    "1309 is a new item.\n",
    "1310 is a new item.\n",
    "1320 is a new item.\n",
    "1343 is a new item.\n",
    "1348 is a new item.\n",
    "1364 is a new item.\n",
    "1373 is a new item.\n",
    "1457 is a new item.\n",
    "1458 is a new item.\n",
    "1492 is a new item.\n",
    "1493 is a new item.\n",
    "1498 is a new item.\n",
    "1505 is a new item.\n",
    "1520 is a new item.\n",
    "1533 is a new item.\n",
    "1536 is a new item.\n",
    "1543 is a new item.\n",
    "1557 is a new item.\n",
    "1561 is a new item.\n",
    "1562 is a new item.\n",
    "1563 is a new item.\n",
    "1565 is a new item.\n",
    "1582 is a new item.\n",
    "1586 is a new item.\n",
    "n_rec_items=10时:\n",
    " \tprecision=0.07559912854030501\n",
    " \trecall=0.01735\n",
    " \tcoverage=0.09575757575757576\n",
    " \trmse=0.9247687112120774\n",
    "\n",
    "\n",
    "推荐20个电影时的结果\n",
    "599 is a new item.\n",
    "711 is a new item.\n",
    "814 is a new item.\n",
    "830 is a new item.\n",
    "852 is a new item.\n",
    "857 is a new item.\n",
    "1156 is a new item.\n",
    "1236 is a new item.\n",
    "1309 is a new item.\n",
    "1310 is a new item.\n",
    "1320 is a new item.\n",
    "1343 is a new item.\n",
    "1348 is a new item.\n",
    "1364 is a new item.\n",
    "1373 is a new item.\n",
    "1457 is a new item.\n",
    "1458 is a new item.\n",
    "1492 is a new item.\n",
    "1493 is a new item.\n",
    "1498 is a new item.\n",
    "1505 is a new item.\n",
    "1520 is a new item.\n",
    "1533 is a new item.\n",
    "1536 is a new item.\n",
    "1543 is a new item.\n",
    "1557 is a new item.\n",
    "1561 is a new item.\n",
    "1562 is a new item.\n",
    "1563 is a new item.\n",
    "1565 is a new item.\n",
    "1582 is a new item.\n",
    "1586 is a new item.\n",
    "n_rec_items=20时:\n",
    " \tprecision=0.07962962962962963\n",
    " \trecall=0.03655\n",
    " \tcoverage=0.15333333333333332\n",
    " \trmse=0.9247687112120774\n",
    "```\n",
    "\n",
    "+ 结果分析\n",
    "\n",
    "(1) 性能比较\n",
    "\n",
    "| 方法 | 第一部分工作 | 耗时 | 第二部分工作 | 耗时 | 第三部分工作 |\n",
    "| :-: | :-: | :-: | :-: | :-: | :-: |\n",
    "| 基于User的CF | 计算所有用户的相似度 | 442.0673秒 | 完成459个User的推荐 | 2297.6894秒 | 计算模型在测试集上的预测结果评价指标 |\n",
    "| 基于Item的CF | 计算1650个Item两两之间的相似度 | 575.1729秒 | 完成459个User的推荐 | 2173.5053秒 | 计算模型在测试集上的预测结果评价指标 |\n",
    "| 基于矩阵分解的CF | 完成50个step的预测模型的训练 | 2084.7492秒 | 完成459个User的推荐 | 896.7403秒 | 计算模型在测试集上的预测结果评价指标 |\n",
    "\n",
    "通过对比可以看出：\n",
    "\n",
    "+ 基于User和基于Item的CF都预先进行了相似度的计算，这个过程耗费了400\\~600秒，时间复杂度为$O(N^2 + M)$ 或者$O(M^2 + N)$，但用来执行推荐时，这个过程耗费了2100\\~2300秒, 时间复杂度为$O(M*N)$；\n",
    "+ 基于矩阵分解的CF，训练过程耗费时间为 2000+秒， 但执行推荐的过程变快了，只用了900秒不到；\n",
    "+ 性能上的差异，主要是因为基于矩阵分解的CF是训练了一个模型，然后用这个模型去进行预测，速度大大加快；而前两种CF方法，并没有训练模型，所以每次做推荐都要从头算一遍，所以不支持离线处理。\n",
    "\n",
    "(2) 不同方法的评价指标比较(推荐10部电影时)\n",
    "\n",
    "| 方法 | precision | recall | coverage | rmse |\n",
    "| :-: | :-: | :-: | :-: | :-: |\n",
    "| 基于User的CF | 0.00087 | 0.0002 | 0.14606 | 3.68616 |\n",
    "| 基于Item的CF | 0.06275 | 0.0144 | 0.48727 | 1.13278 |\n",
    "| 基于矩阵分解的CF | 0.07560 | 0.01735 | 0.09576 | 0.92477 |\n",
    "\n",
    "通过对比可以看出：\n",
    "\n",
    "+ 基于Item的CF在precision, recall, coverage, rmse上的表现，都好于基于User，可能是因为Item相似性相比User相似性较为稳定， 所以能得出更为精准的预测;\n",
    "+ 基于矩阵分解的CF， 在precision, recall, rmse指标上都更好，但在coverage上会略差，可能是因为它是一个拟合较好的模型，既会考虑Item因子，也会考虑User因子，因而相比单纯重视其中一个因子来说，会做到更精准的预测；\n",
    "\n",
    "(3) 推荐10部电影和20部电影时的评价指标对比\n",
    "\n",
    "| 方法 | 推荐电影数 | precision | recall | coverage | rmse |\n",
    "| :-: | :-: | :-: | :-: | :-: | :-: |\n",
    "| 基于User的CF | 10 | 0.00087 | 0.0002 | 0.14606 | 3.68616 |\n",
    "| 基于User的CF | 20 | 0.00174 | 0.0008 | 0.22727 | 3.68616 |\n",
    "\n",
    "| 方法 | 推荐电影数 | precision | recall | coverage | rmse |\n",
    "| :-: | :-: | :-: | :-: | :-: | :-: |\n",
    "| 基于Item的CF | 10 | 0.06275 | 0.0144 | 0.48727 | 1.13278 |\n",
    "| 基于Item的CF | 20 | 0.06590 | 0.03025 | 0.72606 | 1.13278 |\n",
    "\n",
    "| 方法 | 推荐电影数 | precision | recall | coverage | rmse |\n",
    "| :-: | :-: | :-: | :-: | :-: | :-: |\n",
    "| 基于矩阵分解的CF | 10 | 0.07560 | 0.01735 | 0.09576 | 0.92477 |\n",
    "| 基于矩阵分解的CF | 20 | 0.07963 | 0.03655 | 0.15333 | 0.92477 |\n",
    "\n",
    "通过对比可以看出:\n",
    "\n",
    "+ 推荐20部电影相比于10部电影来说，rmse完全不变，precision也相差不大, recall和coverage有倍数级提升,这种现象也很好理解，因为返回的样本多了，所以当precision保持稳定的时候，意味着召回的样本数提升了，即recall和coverage都提升了。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
